/************************************************************
* DS_MULTI_MAP.H                                  12.12.2007
*
* .
************************************************************/
#ifndef _DS_MAP_H_
#define _DS_MAP_H_

#pragma once

//#include "ap/ap_dlstat.h"
#include "ds\ds_vector.h"
#include "ds\ds_algorithm.h"
#include "ds\ds_allocator.h"
#include "ds\ds_named_pair.h"
#include "m3d\m3d.h"

namespace ds {

template <class K, class V, class H, class C, template <class> class A>
class MAP;

namespace impl {

template <class K, class V, class H, class C, template <class> class A>
class MAP_CONST_MULTI_ITERATOR;

template <class K, class V, class H, class C, template <class> class A>
class MAP_MULTI_ITERATOR;

template <class K, class V, class H, class C, template <class> class A>
class MAP_ITERATOR;

#ifndef _RETAIL
template <class iterator>
struct BEGIN_HELPER {
   BEGIN_HELPER(const iterator & iter)
      : iter(iter)
   {}

   iterator iter;
};
#endif

//////////////////////////////////////////////////////////////////////////
// ITERATOR
template <class K, class V, class H, class C, template <class> class A>
class MAP_CONST_ITERATOR {
	friend class ds::MAP<K, V, H, C, A>;
   friend class MAP_CONST_MULTI_ITERATOR<K, V, H, C, A>;
public:
	typedef MAP<K, V, H, C, A>       map_type;
	typedef typename map_type::ITEM  item_type;
	typedef typename map_type::key_type key_type;
	typedef typename map_type::value_type value_type;

public:
	MAP_CONST_ITERATOR(void)
		: container(), item(), index()
	{}

#ifndef _RETAIL
   MAP_CONST_ITERATOR(const BEGIN_HELPER<MAP_CONST_ITERATOR<K, V, H, C, A> > & helper)
      : container(helper.iter.container)
      , item(helper.iter.item)
      , index(helper.iter.index)
   {}

   MAP_CONST_ITERATOR(const BEGIN_HELPER<MAP_ITERATOR<K, V, H, C, A> > & helper);
#endif

   MAP_CONST_ITERATOR(const MAP_CONST_MULTI_ITERATOR<K, V, H, C, A> & multiIter);

	FORCE_INLINE MAP_CONST_ITERATOR &       operator++ (void);

	inline bool             operator ==    (const MAP_CONST_ITERATOR & p) const;
	inline bool             operator !=    (const MAP_CONST_ITERATOR & p) const { return !(*this == p); }

	inline const value_type & operator *   (void) const;

	inline const value_type * operator ->  (void) const { STRONG_ASSERT(item != NULL); return &item->value; }

	inline const key_type & key            (void) const;
	inline const value_type & value        (void) const;

	inline const value_type * get          (void) const { return IsDone() ? NULL : &**this; }

	inline bool             IsDone         (void) const { return item == NULL; }

protected:
	MAP_CONST_ITERATOR(map_type & container, item_type & item, int index)
		: container(&container), item(&item), index(index)
	{}

private:
	map_type *           container;
	item_type *          item;
	int                  index;
};

template <class K, class V, class H, class C, template <class> class A>
class MAP_ITERATOR : public MAP_CONST_ITERATOR<K, V, H, C, A> {
	friend class ds::MAP<K, V, H, C, A>;
public:
	MAP_ITERATOR(void) {}
   MAP_ITERATOR(const MAP_MULTI_ITERATOR<K, V, H, C, A> & multiIter);

#ifndef _RETAIL
   MAP_ITERATOR(const BEGIN_HELPER<MAP_ITERATOR<K, V, H, C, A> > & helper)
      : MAP_CONST_ITERATOR<K, V, H, C, A>(helper.iter)
   {}
#endif

	typedef MAP<K, V, H, C, A>       map_type;
	typedef typename map_type::ITEM  item_type;
	typedef typename map_type::key_type key_type;
	typedef typename map_type::value_type value_type;

protected:
	MAP_ITERATOR(map_type & container, item_type & item, int index)
		: MAP_CONST_ITERATOR<K,V,H,C,A>(container, item, index)
	{}

public:
	FORCE_INLINE MAP_ITERATOR & operator++ (void) { this->MAP_CONST_ITERATOR<K,V,H,C,A>::operator ++(); return *this; }

	inline typename MAP_CONST_ITERATOR<K,V,H,C,A>::value_type &     operator *     (void) const { return const_cast<typename MAP_CONST_ITERATOR<K,V,H,C,A>::value_type &> (this->MAP_CONST_ITERATOR<K,V,H,C,A>::operator * ()); }
	inline typename MAP_CONST_ITERATOR<K,V,H,C,A>::value_type *     operator ->    (void) const { return const_cast<typename MAP_CONST_ITERATOR<K,V,H,C,A>::value_type *> (this->MAP_CONST_ITERATOR<K,V,H,C,A>::operator -> ()); }

	inline typename MAP_CONST_ITERATOR<K,V,H,C,A>::value_type &     value          (void) const { return const_cast<typename MAP_CONST_ITERATOR<K,V,H,C,A>::value_type &> (this->MAP_CONST_ITERATOR<K,V,H,C,A>::value()); }

	inline typename MAP_CONST_ITERATOR<K,V,H,C,A>::value_type *     get            (void) const { return const_cast<typename MAP_CONST_ITERATOR<K,V,H,C,A>::value_type *> (this->MAP_CONST_ITERATOR<K,V,H,C,A>::get()); }
};

//////////////////////////////////////////////////////////////////////////
// MULTI ITEREATOR
template <class K, class V, class H, class C, template <class> class A>
class MAP_CONST_MULTI_ITERATOR {
	friend class ds::MAP<K, V, H, C, A>;
   friend class MAP_ITERATOR<K, V, H, C, A>;
   friend class MAP_CONST_ITERATOR<K, V, H, C, A>;
public:
	typedef MAP<K, V, H, C, A>       map_type;
	typedef typename map_type::ITEM  item_type;
	typedef typename map_type::key_type key_type;
	typedef typename map_type::value_type value_type;
	typedef typename map_type::const_iterator const_iterator;

public:
	MAP_CONST_MULTI_ITERATOR(void)
		: container(), item()
	{}

	MAP_CONST_MULTI_ITERATOR(const MAP_CONST_ITERATOR<K, V, H, C, A> & p)
		: container(p.container), item(p.item)
	{}

	FORCE_INLINE MAP_CONST_MULTI_ITERATOR & operator++ (void);

	inline bool             operator ==    (const MAP_CONST_MULTI_ITERATOR & p) const;
	inline bool             operator !=    (const MAP_CONST_MULTI_ITERATOR & p) const { return !(*this == p); }

	inline const value_type & operator *   (void) const;

	inline const value_type * operator ->  (void) const { STRONG_ASSERT(item != NULL); return &item->value; }

   inline const key_type & key            (void) const { STRONG_ASSERT(item != NULL); return item->key; }
	inline const value_type & value        (void) const { STRONG_ASSERT(item != NULL); return item->value; }

	inline const value_type * get          (void) const { return IsDone() ? NULL : &**this; }

	inline bool             IsDone         (void) const { return item == NULL; }

#ifndef _RETAIL
private:
   MAP_CONST_MULTI_ITERATOR(const BEGIN_HELPER<MAP_CONST_ITERATOR<K, V, H, C, A> > & helper);
#endif

private:
	map_type *              container;
	item_type *             item;
};

template <class K, class V, class H, class C, template <class> class A>
class MAP_MULTI_ITERATOR : public MAP_CONST_MULTI_ITERATOR<K, V, H, C, A> {
	friend class ds::MAP<K, V, H, C, A>;
public:
	MAP_MULTI_ITERATOR(void) {}

	MAP_MULTI_ITERATOR(const MAP_ITERATOR<K,V,H,C,A> & p)
		: MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>(p)
	{}

	typedef MAP<K, V, H, C, A>       map_type;
	typedef typename map_type::ITEM  item_type;
	typedef typename map_type::key_type key_type;
	typedef typename map_type::value_type value_type;

public:
	FORCE_INLINE MAP_MULTI_ITERATOR & operator++ (void) { this->MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::operator ++(); return *this; }

	inline typename MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::value_type &     operator *     (void) const { return const_cast<typename MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::value_type &> (this->MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::operator * ()); }
	inline typename MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::value_type *     operator ->    (void) const { return const_cast<typename MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::value_type *> (this->MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::operator -> ()); }

	inline typename MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::value_type &     value          (void) const { return const_cast<typename MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::value_type &> (this->MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::value()); }

	inline typename MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::value_type *     get            (void) const { return const_cast<typename MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::value_type *> (this->MAP_CONST_MULTI_ITERATOR<K,V,H,C,A>::get()); }

#ifndef _RETAIL
private:
   MAP_MULTI_ITERATOR(const BEGIN_HELPER<MAP_ITERATOR<K, V, H, C, A> > & helper);
#endif
};

} // namespace impl

#ifndef _RETAIL
#define DS_BEGIN_HELPER(iterator) \
   impl::BEGIN_HELPER<iterator>
#else
#define DS_BEGIN_HELPER(iterator) \
   iterator
#endif

//////////////////////////////////////////////////////////////////////////
// MAP
template <class K, class V = int, class H = HASH, class C = CMP, template <class AT> class A = dsNODE_CACHE_ALLOCATOR>
class MAP {
public:
	typedef K key_type;
	typedef V value_type;
	typedef H hash_type;
	typedef C cmp_type;

	struct ITEM {
		ITEM *      next;
		key_type    key;
		value_type  value;

		ITEM(const key_type & key, const value_type & value)
			: next(NULL)
			, key(key)
			, value(value)
		{}
	};

	typedef struct DUMMY {
		union {
			struct {
				DUMMY * pNext;
				DUMMY * pPrev;
			};
			char dummy[sizeof(ITEM)];
		};
	} dummy_type;
	typedef A<dummy_type> allocator_type;

	template <class K0, class V0, class H0, class C0, template <class> class A0>
	friend class impl::MAP_CONST_ITERATOR;
	typedef impl::MAP_ITERATOR<K, V, H, C, A> iterator;
	typedef impl::MAP_CONST_ITERATOR<K, V, H, C, A> const_iterator;

	template <class K0, class V0, class H0, class C0, template <class> class A0>
	friend class impl::MAP_CONST_MULTI_ITERATOR;
	typedef impl::MAP_MULTI_ITERATOR<K, V, H, C, A> multi_iterator;
	typedef impl::MAP_CONST_MULTI_ITERATOR<K, V, H, C, A> const_multi_iterator;

	typedef dsNAMED_PAIR_T(iterator, value, bool, wasReplaced) result_type;

	typedef iterator              ITERATOR; // saber and stl compatibility
	typedef const_iterator        CONST_ITERATOR;

	enum {
		MAXDATA           = 5,     // count > MAXDATA   * size
		MAXDATA_2         = 3,     // count > MAXDATA_2 * size && maxdepth > MAXDEPTH
		MAXDATA_3         = 2,     // count > MAXDATA_3 * size && maxdepth > MAXDEPTH
		MAXDEPTH          = 10,
		MAXDEPTH_2        = 25,    // assert(maxdepth < MAXDEPTH_2);
		SIZE_MULT         = 2,     // resize(size * SIZE_MULT);
		DEFAULT_SIZE      = 17,    // size when trying to insert in empty hash
	};

public:
	MAP                  (AP_CL_DECL);
	MAP                  (const MAP<K, V, H, C, A> &map);
	void                 operator =     (const MAP<K, V, H, C, A> &);
	~MAP                 (void)         { Clear(); }

	result_type          Insert         (const key_type & key, const value_type & value = value_type());

	// ADD NEW element, to use this map as multi_map
	iterator					InsertNew		(const key_type & key, const value_type & value = value_type());

	int                  Erase          (const key_type & key);
	iterator             Erase          (iterator iter);
	multi_iterator       Erase          (multi_iterator iter);
   void                 Clear          (void);
   void                 Free           (void);

   DS_BEGIN_HELPER(iterator)           Begin          (void);
#ifndef _RETAIL
   DS_BEGIN_HELPER(const_iterator)     Begin          (void) const { return const_cast<MAP *> (this)->Begin().iter; }
#else
   const_iterator                      Begin          (void) const { return const_cast<MAP *> (this)->Begin(); }
#endif

   iterator             Find           (const key_type & key);
	const_iterator       Find           (const key_type & key) const { return const_cast<MAP *> (this)->Find(key); }

	template <class K1>
	iterator             Find           (const K1 & key);
	template <class K1>
	const_iterator       Find           (const K1 & key) const { return const_cast<MAP *> (this)->Find(key); }

	inline iterator      FindInsert     (const key_type & key, const value_type & value = value_type());

	bool                 Contains       (const key_type & key, value_type * value = NULL) const;

	void                 HashResize     (int size);
	int                  HashSize       (void) const { return data.Length(); }
	int                  Length         (void) const { return count; }

	bool                 IsEmpty        (void) const { return count == 0; }

	void                 Swap           (MAP<K, V, H, C> & p);

#ifdef __PLUGIN__
   struct APPEND_HELPER;
   APPEND_HELPER        operator +=    (const key_type & key);
#endif

private:
	inline bool          TryToResize    (int depth);
	inline void          Insert         (ITEM *& item, const key_type & key, const value_type & value);
	inline void          Delete         (ITEM * ptr) { ptr->~ITEM(); allocator.Delete((dummy_type *)ptr); }

	void						GenHashes		(void);

	template <class T0>
	FORCE_INLINE int		GetHash			(const T0 & key) const;

private:
	UINT						a, b;

	int                  count;
	dsVECTOR<ITEM *>     data;
	allocator_type       allocator;
#ifdef AP_USE_MEM_STAT
	apCL                 cl;
#endif
};

#include "ds_map.hpp"

} // namespace ds

#endif // _DS_MAP_H_
